/*
 * @lc app=leetcode.cn id=131 lang=javascript
 *
 * [131] 分割回文串
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  /**
   * @description: 回溯
   * @param {string*} str
   * @param {number} idx 递归用的索引
   * @param {[[string]]} res
   * @param {[string]} store 存储分割的字符串
   * @return {void}
   */
  const backtrack = (str, idx, res, store) => {
    if (idx === str.length) {
      res.push([...store]);
      return;
    }

    for (let i = idx; i < str.length; i++) {
      const substr = str.substring(idx, i + 1);
      if (memo.get(substr) === false) continue;
      if (memo.get(substr) === true || isPlalindrome(substr, memo)) {
        store.push(substr);
        backtrack(str, i + 1, res, store, memo);
        store.pop();
      }
    }
  };
  /**
   * @description: 判断是否回文
   * @param {string} str
   * @return {bollean}
   */
  const isPlalindrome = (str, memo) => {
    let i = 0;
    let j = str.length - 1;
    while (i < j) {
      if (str[i++] !== str[j--]) {
        memo.set(str, false);
        return false;
      }
    }
    memo.set(str, true);
    return true;
  };

  const result = [];
  const memo = new Map();
  backtrack(s, 0, result, [], memo);

  return result;
};
// @lc code=end
